package C056;

/**
 * ClassName: c02
 * Package: C056
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/4/25 00:10
 * @Version 1.0
 * @Since 1.0
 */
public class c02 {
    public static void main(String[] args) {
        int[] arr = {0,2,1,3};
        System.out.println(minSwapsCouples(arr));
    }


    static int MAXLEN = 100;
    static int[] stack = new int[MAXLEN];
    static int[] father = new int[MAXLEN];
    static int set;
    static int[] arr;
    public static int minSwapsCouples(int[] row) {
        arr = row;
        build();
        for (int i = 0; i < arr.length; i+=2) {
            union(arr[i] >> 1, arr[i + 1] >> 1);
        }
        return arr.length / 2 - set;
    }

    private static void union(int i, int j) {
        int fatheri = find(i);
        int fatherj = find(j);
        if(fatherj == fatheri) {
            return;
        }
        // 合并
        father[fatherj] = fatheri;
        set --;
    }

    // 扁平化
    private static int find(int i) {
        int size = 0;
        while(father[i] != i) {
            stack[size ++] = i;
            i = father[i];
        }

        // 扁平化
        while(size > 0) {
            father[stack[-- size]] = i;
        }
        return i;
    }

    private static void build() {
        for (int i = 0; i < arr.length / 2; i++) {
            father[i] = i;
        }
        set = arr.length / 2;
    }
}
